It is often the case that a physical system or object having a modest number of degrees of freedom is measured with an apparatus that has many more degrees of freedom than the system or object. For example, a human face has a few hundred (d) degrees of freedom, while a single digital mega-pixel image of the human face has many million (D) degrees of freedom, for example, i.e., at least three color intensities for each pixel, and thus d<<D.
The space of all possible images of varied facial expressions is thus a low-dimensional manifold embedded in the high-dimensional sample space of all possible digital images. Herein, a manifold is exemplified by a smooth 2D surface embedded in a 3D space (coordinate system), and more generally defined as a connected subregion of a high-dimensional space that can be flattened to yield a lower-dimensional space that preserves the connectivity structure of local neighborhoods in the subregion.
In the context of the present invention, a manifold is a representation of all possible configurations of a measured physical system or object. For example, embedded in the high-dimensional space of all possible images of a hand there is a 22-dimensional manifold representing all possible joint angles. The invention shows how to estimate and use this manifold and its embedding from a finite number of measurements, e.g., a set of digital images.
In the field of mathematics known as differential geometry, charting is known as the problem of assigning a local low-dimensional coordinate system to every point on a manifold whose geometry is known analytically, e.g., characterized by mathematical formulae. Of particular interest is the case where these local charts can be connected to give a globally consistent chart, which assigns a unique low-dimensional coordinate.
In the present invention, it is shown how to perform analogous operations on measured data in a high-dimensional sample space of real-world physical systems. The invention uses the chart to edit, visualize or render, compress, de-noise, and otherwise manipulate the measured signal while preserving the fidelity of the results.
With charting, it is presumed that the data lie on or near some low-dimensional manifold embedded in the sample space, and that there exists a one-to-one smooth non-linear transform between the manifold and a low-dimensional vector space.
It is desired to estimate smooth continuous mappings between the sample and coordinate spaces. Often this analysis sheds light on intrinsic variables of the data-generating phenomenon, for example, revealing perceptual or configuration spaces.
Topology-neutral non-linear dimensionality reduction processes can be divided into those that determine mappings, and those that directly determine low-dimensional embeddings.
DeMers et al., in “Nonlinear Dimensionality Reduction,” Advances in Neural Information Processing Systems, Volume 5, 1993, described how auto-encoding neural networks with a hidden layer “bottleneck,” can be used to effectively cast dimensionality reduction as a compression problem.
Hastie et al., defined principal curves as non-parametric ID curves that pass through the center of “nearby” data samples in “Principal Curves,” J. Am. Statistical Assoc, 84(406):502-516, 1989.
A number of known methods properly regularize that approach and extend it to surfaces, see Smola et al., in “Regularized Principal Manifolds,” Machine Learning, 1999. They provided an analysis of such methods in the broader framework of regularized quantization methods, and developed an iterative process as a means of investigating sample complexity.
A number of significant advances have been made recently in embedding processes. Gomes et al., in “A variational approach to recovering a manifold from sample points,” Proc. ECCV, 2002, treated manifold completion as an anisotropic diffusion problem where sample points are iteratively expanded until they connect to their neighbors.
The ISOMAP process represented remote distances as sums of a trusted set of distances between immediate neighbors, and used multi-dimensional scaling to determine a low-dimensional embedding that minimally distorts all distances, see Tenenbaum et al., “A Global Geometric Framework For Nonlinear Dimensionality Reduction,” Science, 290:2319-2323, Dec. 22, 2000.
A locally linear embedding (LLE) method represented each sample point as a weighted combination of its trusted nearest neighbors, then determined a low-dimensional embedding that minimally distorted these barycentric coordinates, see Roweis et al., “Nonlinear Dimensionality Reduction By Locally Linear Embedding,” Science, 290:2323-2326, Dec. 22, 2000.
Those methods have complementary strengths: ISOMAP handles missing data well but fails if the data hull are non-convex; and vice versa for the LLE method. Both offer embeddings without mappings. However, trusted-set methods are vulnerable to noise because they only consider the subset of point-to-point relationships that tend to have the lowest signal-to-noise relationship. It is known that trusted methods can be unstable because small changes to the size of the trusted neighbor set can induce large changes in the set of constraints that the low-dimensional embedding must satisfy.
In a return to mapping, Roweis et al., in “Global coordination of linear models, “Advances in Neural Information Processing Systems,” Volume 13, 2002, described global coordination. In that method, a mixture of locally linear projections from sample to coordinate space are learned. They devised a posterior probability measure that penalizes distortions in the mapping, and gave an expectation-maximization (EM) rule for locally maximizing the posterior probability.
That work heralded an intriguing new use of variational methods to learn representations, but also highlighted the difficulty of even hill-climbing their multi-modal posterior probability.
It is desired to provide a method for charting a manifold that is a closed-form solution and avoids hill-climbing a non-uniform posterior probability, and to find mappings between sample space and charting space.